package codingforgreat.lchot150;

public class Lc215 {
    public int findKthLargest(int[] nums, int k) {
        if(nums == null || nums.length < k){
            return 0;
        }
        int N = nums.length;
        int[] mid = null;
        //求下标在N - k 处的元素
        int L = 0;
        int R = N - 1;
        while(mid == null || mid[0] > N -k || mid[1] < N - k ){
            swap(nums,R,(int)(Math.random() * (R - L + 1)) + L);
            mid = partition(nums,L,R);
            if(mid[0] <= N - k && mid[1] >= N - k){
                return nums[mid[0]];
            }else if(N -k  < mid[0]){
                R = mid[0] - 1;
            }else{
                L = mid[1] + 1;
            }
        }
        return nums[L];
    }
    public int[] partition(int[] nums,int L,int R){
        if(L == R){
            return new int[]{L,R};
        }
        if(L > R){
            return new int[]{-1,-1};
        }
        int target = nums[R];
        int left = L;
        int right = R + 1;
        int cur = L;
        while(cur < right){
            if(nums[cur] == target){
                cur++;
            }else if(nums[cur] < target){
                swap(nums,left++,cur++);
            }else{
                swap(nums,cur,--right);
            }
        }
        return new int[]{left,right - 1};
    }
    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
